/*
    * Copyright (C) 2010 The Guava Authors
    *
    * Licensed under the Apache License, Version 2.0 (the "License");
    * you may not use this file except in compliance with the License.
    * You may obtain a copy of the License at
    *
    * http://www.apache.org/licenses/LICENSE-2.0
    *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  package com.google.common.collect;
  
  import com.google.caliper.BeforeExperiment;
  import com.google.caliper.Benchmark;
  import com.google.caliper.Param;
  import com.google.common.base.Function;
  import com.google.common.collect.ForwardingQueue;
  import com.google.common.collect.MinMaxPriorityQueue;
  import com.google.common.collect.Ordering;
  
  import java.math.BigInteger;
  import java.util.Comparator;
  import java.util.PriorityQueue;
  import java.util.Queue;
  import java.util.Random;
  
  /**
   * Benchmarks to compare performance of MinMaxPriorityQueue and PriorityQueue.
   * 
   * @author Sverre Sundsdal
   */
  public class MinMaxPriorityQueueBenchmark {
    @Param private ComparatorType comparator;
  
    // TODO(kevinb): add 1000000 back when we have the ability to throw
    // NotApplicableException in the expensive comparator case.
    @Param({"100", "10000"}) private int size;
  
    @Param private HeapType heap;
  
    private Queue<Integer> queue;
  
    private final Random random = new Random();
  
    @BeforeExperiment void setUp() {
      queue = heap.create(comparator.get());
      for (int i = 0; i < size; i++) {
        queue.add(random.nextInt());
      }
    }
    
    @Benchmark void pollAndAdd(int reps) {
      for (int i = 0; i < reps; i++) {
        // TODO(kevinb): precompute random #s?
        queue.add(queue.poll() ^ random.nextInt()); 
      }
    }
  
    @Benchmark void populate(int reps) {
      for (int i = 0; i < reps; i++) {
        queue.clear();
        for (int j = 0; j < size; j++) {
          // TODO(kevinb): precompute random #s?
          queue.add(random.nextInt());
        }
      }
    }
  
    /**
     * Implementation of the InvertedMinMaxPriorityQueue which forwards all calls to
     * a MinMaxPriorityQueue, except poll, which is forwarded to pollMax. That way
     * we can benchmark pollMax using the same code that benchmarks poll.
     */
    static final class InvertedMinMaxPriorityQueue <T> extends ForwardingQueue<T> {
      MinMaxPriorityQueue<T> mmHeap;
      public InvertedMinMaxPriorityQueue(Comparator<T> comparator) {
        mmHeap = MinMaxPriorityQueue.orderedBy(comparator).create();
      }
      
      @Override
      protected Queue<T> delegate() {
        return mmHeap;
      }
      
      @Override
      public T poll() {
        return mmHeap.pollLast();
      }
      
    }
  
    public enum HeapType {
      MIN_MAX {
       @Override public Queue<Integer> create(Comparator<Integer> comparator) {
         return MinMaxPriorityQueue.orderedBy(comparator).create();
       }
     },
     PRIORITY_QUEUE {
       @Override public Queue<Integer> create(Comparator<Integer> comparator) {
         return new PriorityQueue<Integer>(11, comparator);
       }
     },
     INVERTED_MIN_MAX {
       @Override public Queue<Integer> create(Comparator<Integer> comparator) {
         return new InvertedMinMaxPriorityQueue<Integer>(comparator);
       }
     };
 
     public abstract Queue<Integer> create(Comparator<Integer> comparator);
   }
   
   /**
    * Does a CPU intensive operation on Integer and returns a BigInteger 
    * Used to implement an ordering that spends a lot of cpu.
    */
   static class ExpensiveComputation implements Function<Integer, BigInteger> {
     @Override
     public BigInteger apply(Integer from) {
       BigInteger v = BigInteger.valueOf(from);
       // Math.sin is very slow for values outside 4*pi
       // Need to take absolute value to avoid inverting the value.
       for (double i = 0; i < 100; i += 20) {
         v = v.add(v.multiply(
             BigInteger.valueOf(
                 ((Double) Math.abs(Math.sin(i) * 10.0)).longValue())));
       }
       return v;
     }
   }
 
   public enum ComparatorType {
     CHEAP {
       @Override public Comparator<Integer> get() {
         return Ordering.natural();
       }
     },
     EXPENSIVE {
       @Override public Comparator<Integer> get() {
         return Ordering.natural().onResultOf(new ExpensiveComputation());
       }
     };
     public abstract Comparator<Integer> get();
   }
 }